iT邦幫忙

2024 iThome 鐵人賽

DAY 30
0
佛心分享-刷題不只是刷題

C/C++ 刷題30天系列 第 30

Day30__C語言刷LeetCode_Sort

  • 分享至 

  • xImage
  •  

竟然到了最後一天,所有跟韌體相關的Easy題目只要能用C語言去解的,都解完了(有些有多種解法)
堅持了30天,之後應該還是會每天刷一題Medium來保持手感,該好好了解其他韌體相關知識了~
(但還是先玩個電腦再說XD)

1752. Check if Array Is Sorted and Rotated

tags: Easy、Sort

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.
There may be duplicates in the original array.
Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

解法1:

bool isSort(int* nums, int numsSize) {
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < nums[i-1]) {
            return false;
        }
    }
    return true;
}


bool check(int* nums, int numsSize) {
    if (isSort(nums, numsSize)) {
        return true;
    }
    int count = 0;
    
    for (int i = 1; i < numsSize; i++) {
        if (nums[i-1] > nums[i]) {
            count++;
        }
        if (count >= 2) {
            return false;
        }
    }
    
    if (nums[0] < nums[numsSize-1]) {
        return false;
    }
    return true;
}

解法2:

bool check(int* nums, int numsSize) {
    int count = 0;
    
    for (int i = 1; i < numsSize; i++) {
        if (nums[i-1] > nums[i]) {
            count++;
        }
    }

    if (nums[0] < nums[numsSize-1]) {
        count++;
    }
    
    return count <= 1;
}

1287. Element Appearing More Than 25% In Sorted Array

tags: Easy、Sort

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.

解法1:

int findSpecialInteger(int* arr, int arrSize) {
    int more = arrSize / 4;
    
    for (int i = 0; i < arrSize; ) {
        int count = 1; //計算當前數字的本身
        while (i + count < arrSize && arr[i+count] == arr[i]) {
            count++;
        }
        if (count > more) {
            return arr[i];
        }
        i += count;
    }
    return -1;
}

解法2:

int findSpecialInteger(int* arr, int arrSize) {
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] == arr[i + (arrSize/4)]) {
            return arr[i];
        }
    }
    return -1;
}

148. Sort List

tags: Medium、Sort

Given the head of a linked list, return the list after sorting it in ascending order.

解法: MergeSort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* splitList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* prev = NULL;

    while (fast != NULL && fast->next != NULL) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = NULL;
    return slow;
}

struct ListNode* mergeLists(struct ListNode* t1, struct ListNode* t2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;

    while (t1 != NULL && t2 != NULL) {
        if (t1->val <= t2->val) {
            tail->next = t1;
            t1 = t1->next;
        }
        else {
            tail->next = t2;
            t2 = t2->next;
        }
        tail = tail->next;
    }

    if (t1) {tail->next = t1;}
    if (t2) {tail->next = t2;}

    return dummy.next;
}

struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    struct ListNode* mid = splitList(head);
    struct ListNode* left = sortList(head);
    struct ListNode* right = sortList(mid);
    
    return mergeLists(left, right);
}

上一篇
Day29__C語言刷LeetCode_Sort
系列文
C/C++ 刷題30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言